package edu.columbia.aicheckers.agent;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.HashMap;
import java.util.Random;

import edu.columbia.aicheckers.CheckerGame;
import edu.columbia.aicheckers.model.Color;
import edu.columbia.aicheckers.model.IBoardState;
import edu.columbia.aicheckers.model.Move;

public class GeneticAgent implements IAgent{
	
	static final int ATTRIBUTE_NUM = AgentHelper.NUM_ATTRIBUTES;

	public static double DEFAULT_THRESHOLD = 0.70; // After a single 
	
	BitSet attributes = new BitSet();
	Random rand = new Random();
	AgentHelper helper;
	
	
	static HashMap<Class,int[]> trainedAttributes = new HashMap<Class,int[]>();
	
	static
	{
		trainedAttributes.put(RuleBasedAgent.class, new int[]{0, 1, 3, 4, 5, 6, 8, 9, 11});
	}
	
	public GeneticAgent(Class opponentType)
	{
		if(trainedAttributes.containsKey(opponentType))
		{
			int[] trained = trainedAttributes.get(opponentType);
			for(int i = 0;i < trained.length; i++)
			{
				attributes.set(trained[i]);
			}
		}
		helper = new AgentHelper(attributes);
	}
	
	protected void createdRandomAttributes()
	{

		for(int i = 0;i < ATTRIBUTE_NUM; i++)
		{
			if(rand.nextBoolean())
			{
				attributes.set(i);
			}
		}
		
	}
	
	public GeneticAgent()
	{
		createdRandomAttributes();
		helper = new AgentHelper(attributes);
	}
	
	public GeneticAgent(BitSet set)
	{
		this.attributes = set;
		helper = new AgentHelper(attributes);
	}
	
	public Move doPly(IBoardState board, Color myColor) {
		// TODO Auto-generated method stub
		return helper.moveSelection(board, myColor, true);
	}
	
	public static void geneticTrain(int numStartingAgents,int numGenerations, int trainingIterations, Class agentType) throws Exception
	{
		//Initialize agents
		ArrayList<GeneticAgent> agents = new ArrayList<GeneticAgent>();		
		for(int i = 0;i < numStartingAgents; i++)
		{
			agents.add(new GeneticAgent());
		}
		GeneticAgent bestAgent = null;
		// Iterate through the generations
		for(int g = 0; g < numGenerations; g++)
		{
			// one generation
			System.out.println("Generation " + g);
			ArrayList<Double> fitnessValues = singleGeneration(agents, trainingIterations, agentType);
			
			// remove 50% unfit agents
			selection(fitnessValues,agents,DEFAULT_THRESHOLD);
		
			if(g == numGenerations-1)
			{
				double max = Double.MIN_VALUE;
				
				// Select best agent
				for(int n = 0;n < agents.size(); n++)
				{
					if(max < fitnessValues.get(n))
					{
						max = fitnessValues.get(n);
						bestAgent = agents.get(n);
					}
				}
				
				System.out.println("Best Agent: " +  bestAgent.toString() + " - Fitness Function : " + max);
				return;
			}
			else
			{
				// Crossover & Mutations
				crossover(agents, numStartingAgents);
			}
		}
		
	}
	
	private static void crossover(ArrayList<GeneticAgent> agents,int numStartingAgents) {
		
		int missingAgents = numStartingAgents - agents.size();
		ArrayList<GeneticAgent> newAgents = new ArrayList<GeneticAgent>();
		Random r = new Random();
		// Create random agents using a one-point crossover
		while(newAgents.size() < missingAgents)
		{
			for(GeneticAgent parent : agents)
			{
				// Create an offspring with another agent (randomly)
				BitSet set = new BitSet(ATTRIBUTE_NUM);
				set.clear();
				int otherParent = r.nextInt(agents.size());
				int crossoverPoint = r.nextInt(ATTRIBUTE_NUM);
				BitSet upperHalf = parent.attributes;
				BitSet lowerHalf = agents.get(otherParent).attributes;
				
				for(int i =  upperHalf.nextSetBit(0); i >= 0 && i < crossoverPoint; i = upperHalf.nextSetBit(i+1))
				{
					set.set(i);
				}
				for(int i = upperHalf.nextSetBit(crossoverPoint); i >= 0; i = lowerHalf.nextSetBit(i+1))
				{
					set.set(i);
				}
				
				GeneticAgent offspring = new GeneticAgent(set);
				newAgents.add(offspring);
			}
		}
		
		for(int i = 0; i < missingAgents; i++)
		{
			agents.add(newAgents.get(i));
		}
		
	}

	private static void selection(ArrayList<Double> fitnessValues, ArrayList<GeneticAgent> agents, double default_threshold) {
		ArrayList<GeneticAgent> inferiorAgents = new ArrayList<GeneticAgent>();
		
		int numToKeep = (int)(default_threshold * (double)agents.size());
		
		numToKeep = numToKeep == 0 ? 1 : numToKeep;
		int numToThrowAway = agents.size() - numToKeep;
		ArrayList<Double> sortedFitnessValues = new ArrayList<Double>(fitnessValues);
		Collections.sort(sortedFitnessValues);
		
		// Find the actual fitness threshold
		double min = sortedFitnessValues.get(sortedFitnessValues.size() - numToKeep);
		
		for(int i = 0;i < fitnessValues.size() && inferiorAgents.size() < numToThrowAway; i++)
		{
			double d = fitnessValues.get(i);

			if(d <= min)
			{
				inferiorAgents.add(agents.get(i));
			}

		}
		
		for(GeneticAgent a : inferiorAgents)
		{
			agents.remove(a);
		}
	}

	private static ArrayList<Double> singleGeneration(ArrayList<GeneticAgent> agents,int trainingIterations, Class agentType) throws Exception
	{
		ArrayList<Double> fitnessValues = new ArrayList<Double>();
		for(int n = 0; n < agents.size(); n++)
		{	
			IAgent opponent = (IAgent)agentType.newInstance();
			IAgent currentAgent = agents.get(n);
			fitnessValues.add(fitnessFunction(trainingIterations,currentAgent,opponent));
		}
		return fitnessValues;
	}
	
	private static double fitnessFunction(int trainingIterations,IAgent currentAgent, IAgent opponent)
	{
		int numWins = 0;
		boolean iStart = false;
		for(int i = 0;i < trainingIterations; i++)
		{
			if(iStart)
			{
				CheckerGame game = new CheckerGame(currentAgent,opponent);
				game.setPrintDebugInfo(false);
				Color color = game.start();
				if(color == Color.White)
				{
					numWins++;
					System.out.print("W");
				}
				else if(color == Color.White)
				{
					System.out.print("L");
				}
				else
				{
					System.out.print(".");
				}
			}
			else
			{
				CheckerGame game = new CheckerGame(opponent,currentAgent);
				game.setPrintDebugInfo(false);
				Color color = game.start();
				if(color == Color.Black)
				{
					numWins++;
					System.out.print("W");
				}
				else if(color == Color.White)
				{
					System.out.print("L");
				}
				else
				{
					System.out.print(".");
				}
			}
		}
		System.out.println("");
		double percentageWin = 100.0*((double)numWins/(double)trainingIterations);
		System.out.println("Genetic Agent - " + currentAgent.toString() +  " : " + percentageWin + "% wins");
		return percentageWin;
	}
	
	public static void main(String[] args)
	{
		try {
			CheckerGame.STALEMATE_COUNT = 150;
//			GeneticAgent.geneticTrain(15,5,30,RuleBasedAgent.class);
			
			GeneticAgent.geneticTrain(15,5,30,IntelliAgent.class);
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	@Override
	public String toString()
	{
		return "Genetic Agent - attributes: " + this.attributes.toString();
	}

}
